#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

bool CompareNode(ListNode *a, ListNode *b){
    return a->val > b->val;
}


ListNode *mergeKLists(vector<ListNode *> &lists) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(lists.size() == 0)
        return NULL;
    ListNode *pHear = new ListNode(-1);
    ListNode *curNode = pHear;

    vector<ListNode *> channel;
    // init channel
    for(int i=0; i<lists.size(); ++i)
        if(lists[i] != NULL){
            channel.push_back(lists[i]);
        }

    make_heap(channel.begin(), channel.end(), CompareNode);
    // begin
    while(channel.size() > 0){
        pop_heap(channel.begin(), channel.end(), CompareNode);
        curNode->next = *(channel.end() - 1);
        curNode = curNode->next;
        channel.pop_back();
        if(curNode->next != NULL){
            channel.push_back(curNode->next);
        }
        curNode->next = NULL;
        push_heap(channel.begin(), channel.end(), CompareNode);
    }
    return pHear->next;
}

int main(){
    return 0;
}